COCI/2010-2011/Contest #1 - 22.10.2010/ples/ples.2.cpp

   1 // Andrés Mejía
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <numeric>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <string>
  14 #include <cstdio>
  15 #include <vector>
  16 #include <cmath>
  17 #include <queue>
  18 #include <deque>
  19 #include <stack>
  20 #include <list>
  21 #include <map>
  22 #include <set>
  23
  24 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  25 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  26 #define D(x) cout << #x " is " << x << endl
  27
  28 const double EPS = 1e-9;
  29 int cmp(double x, double y = 0, double tol = EPS) {
  30     return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  31 }
  32
  33 /*
  34   ACRush's Dinic algorithm for maximum flow
  35   Complexity: O(E V^2)
  36
  37   Usage:
  38   init(number of nodes, source, sink);
  39   Create graph using add_edge(int u, int v, int c1, int c2):
  40   This adds two directed edges: u -> v with capacity c1
  41     and v -> u with capacity c2.
  42   c2 by default is 0.
  43   After creating the graph, nedge contains the number of
  44      total edges.
  45   dinic_flow();
  46   This doesn't modify the capacity of the original graph,
  47      so you can run the algorithm several times on the same
  48      graph.
  49   If you want to run the algorithm with different sources/sinks
  50      assign the correct value to src and dest before calling
  51      dinic_flow().
  52  */
  53
  54 const int MAXN = 1005;
  55
  56 // namespace Flow {
  57 //     const int maxnode=MAXN * 4 + 2; const int
  58 //     maxedge=(2 * MAXN) * (2 * MAXN + 1) / 2; const int oo=1000000000;
  59 //
  60 //     int node,src,dest,nedge; int
  61 //     head[maxnode],point[maxedge],next[maxedge],
  62 //     flow[maxedge],capa[maxedge];
  63 //     int dist[maxnode],Q[maxnode],work[maxnode];
  64 //
  65 //     void init(int _node,int _src,int _dest) { node=_node;
  66 //     src=_src; dest=_dest; for (int i=0;i<node;i++) head[i]=-1;
  67 //     nedge=0; } void add_edge(int u,int v,int c1,int c2 = 0) {
  68 //     point[nedge]=v,capa[nedge]=c1,flow[nedge]=0,
  69 //     next[nedge]=head[u],head[u]=(nedge++);
  70 //     point[nedge]=u,capa[nedge]=c2,flow[nedge]=0,
  71 //     next[nedge]=head[v],head[v]=(nedge++);
  72 //     } bool dinic_bfs() { memset(dist,255,sizeof(dist));
  73 //     dist[src]=0; int sizeQ=0; Q[sizeQ++]=src; for (int
  74 //     cl=0;cl<sizeQ;cl++) for (int k=Q[cl],i=head[k];i>=0;i=next[i])
  75 //     if (flow[i]<capa[i] && dist[point[i]]<0) {
  76 //     dist[point[i]]=dist[k]+1; Q[sizeQ++]=point[i]; } return
  77 //     dist[dest]>=0; } int dinic_dfs(int x,int exp) { if (x==dest)
  78 //     return exp; for (int &i=work[x];i>=0;i=next[i]) { int
  79 //     v=point[i],tmp; if (flow[i]<capa[i] && dist[v]==dist[x]+1 &&
  80 //     (tmp=dinic_dfs(v,min(exp,capa[i]-flow[i])))>0) { flow[i]+=tmp;
  81 //     flow[i^1]-=tmp; return tmp; } } return 0; } int dinic_flow() {
  82 //     for (int i=0; i<nedge; ++i) flow[i] = 0; int result=0; while
  83 //     (dinic_bfs()) { for (int i=0;i<node;i++) work[i]=head[i];
  84 //     while (1) { int delta=dinic_dfs(src,oo); if (delta==0) break;
  85 //     result+=delta; } } return result; }
  86 // }
  87
  88 /////////////// Maximum flow for sparse graphs ///////////////
  89 ///////////////    Complexity: O(V * E^2)      ///////////////
  90
  91 /*
  92   Usage:
  93   initialize_max_flow();
  94   Create graph using add_edge(u, v, c);
  95   max_flow(source, sink);
  96
  97   WARNING: The algorithm writes on the cap array. The capacity
  98   is not the same after having run the algorithm.  If you need
  99   to run the algorithm several times on the same graph, backup
 100   the cap array.
 101  */
 102
 103 namespace Flow {
 104 const int MAXE = 50000; //Maximum number of edges
 105 const int oo = INT_MAX / 4;
 106 int cap[MAXE];
 107 int first[MAXE];
 108 int next[MAXE];
 109 int adj[MAXE];
 110 int current_edge;
 111
 112 /*
 113   Builds a directed edge (u, v) with capacity c.
 114   Note that actually two edges are added, the edge
 115   and its complementary edge for the backflow.
 116  */
 117 int add_edge(int u, int v, int c){
 118   adj[current_edge] = v;
 119   cap[current_edge] = c;
 120   next[current_edge] = first[u];
 121   first[u] = current_edge++;
 122
 123   adj[current_edge] = u;
 124   cap[current_edge] = 0;
 125   next[current_edge] = first[v];
 126   first[v] = current_edge++;
 127 }
 128
 129 void initialize_max_flow(){
 130   current_edge = 0;
 131   memset(next, -1, sizeof next);
 132   memset(first, -1, sizeof first);
 133 }
 134
 135 int q[MAXE];
 136 int incr[MAXE];
 137 int arrived_by[MAXE];
 138 //arrived_by[i] = The last edge used to reach node i
 139 int find_augmenting_path(int src, int snk){
 140   /*
 141     Make a BFS to find an augmenting path from the source to
 142     the sink.  Then pump flow through this path, and return
 143     the amount that was pumped.
 144   */
 145   memset(arrived_by, -1, sizeof arrived_by);
 146   int h = 0, t = 0;
 147   q[t++] = src;
 148   arrived_by[src] = -2;
 149   incr[src] = oo;
 150   while (h < t && arrived_by[snk] == -1){ //BFS
 151     int u = q[h++];
 152     for (int e = first[u]; e != -1; e = next[e]){
 153       int v = adj[e];
 154       if (arrived_by[v] == -1 && cap[e] > 0){
 155         arrived_by[v] = e;
 156         incr[v] = min(incr[u], cap[e]);
 157         q[t++] = v;
 158       }
 159     }
 160   }
 161
 162   if (arrived_by[snk] == -1) return 0;
 163
 164   int cur = snk;
 165   int neck = incr[snk];
 166   while (cur != src){
 167     //Remove capacity from the edge used to reach node "cur"
 168     //Add capacity to the backedge
 169     cap[arrived_by[cur]] -= neck;
 170     cap[arrived_by[cur] ^ 1] += neck;
 171     //move backwards in the path
 172     cur = adj[arrived_by[cur] ^ 1];
 173   }
 174   return neck;
 175 }
 176
 177 int max_flow(int src, int snk){
 178   int ans = 0, neck;
 179   while ((neck = find_augmenting_path(src, snk)) != 0){
 180     ans += neck;
 181   }
 182   return ans;
 183 }
 184 }
 185
 186 const int src = MAXN * 4, sink = src + 1;
 187
 188 int face(int number, bool isBoy) {
 189     int ans = isBoy ? 0 : 2 * MAXN;
 190     if (number < 0) ans += -number;
 191     else ans += number + MAXN;
 192     ans -= 1500;
 193     //printf("number = %d, isBoy = %d, ans = %d\n", number, isBoy, ans);
 194     assert(ans < 4 * MAXN);
 195     return ans;
 196 }
 197
 198 int cnt[4 * MAXN];
 199
 200 int main(){
 201     int n;
 202     scanf("%d", &n);
 203     for (int i = 0; i < n; ++i) {
 204         int x; scanf("%d", &x);
 205         assert(1500 <= abs(x) and abs(x) <= 2500);
 206         int k = face(x, true);
 207         cnt[k]++;
 208         //printf("cnt[boy = %d] = %d\n", x, cnt[k]);
 209     }
 210     for (int i = 0; i < n; ++i) {
 211         int x; scanf("%d", &x);
 212         assert(1500 <= abs(x) and abs(x) <= 2500);
 213         int k = face(x, false);
 214         cnt[k]++;
 215         //printf("cnt[girl = %d] = %d\n", x, cnt[k]);
 216     }
 217
 218     //Flow::init(Flow::maxnode, src, sink);
 219     Flow::initialize_max_flow();
 220
 221     for (int boy = -2500; boy <= -1500; ++boy) {
 222         if (cnt[face(boy, true)] == 0) continue;
 223         for (int girl = 1500; girl < -boy; ++girl) {
 224             if (cnt[face(girl, false)] == 0) continue;
 225             Flow::add_edge(face(boy, true), face(girl, false), Flow::oo);
 226             //printf("Added edge from boy = %d to girl = %d\n", boy, girl);
 227         }
 228     }
 229
 230     for (int boy = 1500; boy <= 2500; ++boy) {
 231         if (cnt[face(boy, true)] == 0) continue;
 232         for (int girl = -boy-1; girl >= -2500; --girl) {
 233             if (cnt[face(girl, false)] == 0) continue;
 234             Flow::add_edge(face(boy, true), face(girl, false), Flow::oo);
 235             //printf("Added edge from boy = %d to girl = %d\n", boy, girl);
 236         }
 237     }
 238
 239     for (int k = 1500; k <= 2500; ++k) {
 240         if (cnt[face(k, true)] > 0) {
 241             Flow::add_edge(src, face(k, true), cnt[face(k, true)]);
 242         }
 243         if (cnt[face(-k, true)] > 0) {
 244             Flow::add_edge(src, face(-k, true), cnt[face(-k, true)]);
 245         }
 246
 247         if (cnt[face(k, false)] > 0) {
 248             Flow::add_edge(face(k, false), sink, cnt[face(k, false)]);
 249         }
 250
 251         if (cnt[face(-k, false)] > 0) {
 252             Flow::add_edge(face(-k, false), sink, cnt[face(-k, false)]);
 253         }
 254     }
 255
 256     //int ans = Flow::dinic_flow();
 257     int ans = Flow::max_flow(src, sink);
 258     cout << ans << endl;
 259     return 0;
 260 }